package com.arron.algorithm.leetcodetop100.单调队列;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;


public class 滑动窗口最大值 {



    LinkedList<Integer> queue = new LinkedList<>();


    public int[] maxSlidingWindow(int[] nums, int k) {

        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            //将前k-1个数先加入到窗口
            if (i < k-1){
                push(nums[i]);
                continue;
            }
            push(nums[i]);
            res.add(getMax());
            //移除最后一个元素
            pop(nums[i-k+1]);
        }


        return res.stream().mapToInt(Integer::intValue).toArray();
    }


    public void  push(Integer a){

        //将前面比自己小的元素全部删除
        while (!queue.isEmpty() && queue.getLast() < a){
            queue.removeLast();
        }
        queue.addLast(a);
    }


    public void  pop(Integer a){
        if (queue.getFirst().equals(a)){
            queue.pollFirst();
        }
    }


    public Integer getMax(){
        return queue.getFirst();
    }


    public static void main(String[] args) {

        int[] a = {1,3,-1,-3,5,3,6,7};


        滑动窗口最大值 max = new 滑动窗口最大值();
        System.out.println(Arrays.toString(max.maxSlidingWindow(a, 3)));

    }



}
